{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Get Biggest Three Rhombus Sums in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #matrix #prefix-sum #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #矩阵 #前缀和 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getBiggestThree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中最大的三个菱形和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的整数矩阵 <code>grid</code> 。</p>\n",
    "\n",
    "<p><strong>菱形和</strong> 指的是 <code>grid</code> 中一个正菱形 <strong>边界</strong> 上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/23/pc73-q4-desc-2.png\" style=\"width: 385px; height: 385px;\" />\n",
    "<p> </p>\n",
    "\n",
    "<p>注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。</p>\n",
    "\n",
    "<p>请你按照 <strong>降序</strong> 返回 <code>grid</code> 中三个最大的 <strong>互不相同的菱形和</strong> 。如果不同的和少于三个，则将它们全部返回。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/23/pc73-q4-ex1.png\" style=\"width: 360px; height: 361px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]\n",
    "<b>输出：</b>[228,216,211]\n",
    "<b>解释：</b>最大的三个菱形和如上图所示。\n",
    "- 蓝色：20 + 3 + 200 + 5 = 228\n",
    "- 红色：200 + 2 + 10 + 4 = 216\n",
    "- 绿色：5 + 200 + 4 + 2 = 211\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/23/pc73-q4-ex2.png\" style=\"width: 217px; height: 217px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "<b>输出：</b>[20,9,8]\n",
    "<b>解释：</b>最大的三个菱形和如上图所示。\n",
    "- 蓝色：4 + 2 + 6 + 8 = 20\n",
    "- 红色：9 （右下角红色的面积为 0 的菱形）\n",
    "- 绿色：8 （下方中央面积为 0 的菱形）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[7,7,7]]\n",
    "<b>输出：</b>[7]\n",
    "<b>解释：</b>所有三个可能的菱形和都相同，所以返回 [7] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 100</code></li>\n",
    "\t<li><code>1 <= grid[i][j] <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [get-biggest-three-rhombus-sums-in-a-grid](https://leetcode.cn/problems/get-biggest-three-rhombus-sums-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [get-biggest-three-rhombus-sums-in-a-grid](https://leetcode.cn/problems/get-biggest-three-rhombus-sums-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]', '[[1,2,3],[4,5,6],[7,8,9]]', '[[7,7,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        def f(x, y, d):\n",
    "            if d == 0:\n",
    "                return grid[x][y]\n",
    "            res = 0\n",
    "            for i in range(d):\n",
    "                res += grid[x - d + i][y + i] + grid[x + i][y + d - i] + grid[x + d - i][y - i] + grid[x - i][y - d + i]\n",
    "            return res\n",
    "        for d in range((min(r, c) + 1) // 2):  # 表示菱形两个相邻顶点间距\n",
    "            for i in range(d, r - d):   # 枚举菱形中心\n",
    "                for j in range(d, c - d):\n",
    "                    ans.append(f(i, j, d))\n",
    "                    ans = list(set(ans))\n",
    "                    ans.sort(reverse=True)\n",
    "                    if len(ans) > 3:\n",
    "                        ans.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0, 0, 0]\n",
    "    \n",
    "    def put(self, x: int):\n",
    "        _ans = self.ans\n",
    "\n",
    "        if x > _ans[0]:\n",
    "            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1], _ans[2] = x, _ans[1]\n",
    "        elif x != _ans[0] and x != _ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    \n",
    "    def get(self) -> List[int]:\n",
    "        _ans = self.ans\n",
    "\n",
    "        return [num for num in _ans if num != 0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum1 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "        sum2 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                sum1[i][j] = sum1[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "                sum2[i][j] = sum2[i - 1][j + 1] + grid[i - 1][j - 1]\n",
    "        \n",
    "        ans = Answer()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 单独的一个格子也是菱形\n",
    "                ans.put(grid[i][j])\n",
    "                for k in range(i + 2, m, 2):\n",
    "                    ux, uy = i, j\n",
    "                    dx, dy = k, j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    \n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    \n",
    "                    ans.put(\n",
    "                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +\n",
    "                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +\n",
    "                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +\n",
    "                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -\n",
    "                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])\n",
    "                    )\n",
    "        \n",
    "        return ans.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0, 0, 0]\n",
    "    \n",
    "    def put(self, x: int):\n",
    "        _ans = self.ans\n",
    "\n",
    "        if x > _ans[0]:\n",
    "            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1], _ans[2] = x, _ans[1]\n",
    "        elif x != _ans[0] and x != _ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    \n",
    "    def get(self) -> List[int]:\n",
    "        _ans = self.ans\n",
    "\n",
    "        return [num for num in _ans if num != 0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum1 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "        sum2 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                sum1[i][j] = sum1[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "                sum2[i][j] = sum2[i - 1][j + 1] + grid[i - 1][j - 1]\n",
    "        \n",
    "        ans = Answer()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 单独的一个格子也是菱形\n",
    "                ans.put(grid[i][j])\n",
    "                for k in range(i + 2, m, 2):\n",
    "                    ux, uy = i, j\n",
    "                    dx, dy = k, j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    \n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    \n",
    "                    ans.put(\n",
    "                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +\n",
    "                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +\n",
    "                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +\n",
    "                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -\n",
    "                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])\n",
    "                    )\n",
    "        \n",
    "        return ans.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0, 0, 0]\n",
    "    \n",
    "    def put(self, x: int):\n",
    "        _ans = self.ans\n",
    "\n",
    "        if x > _ans[0]:\n",
    "            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1], _ans[2] = x, _ans[1]\n",
    "        elif x != _ans[0] and x != _ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    \n",
    "    def get(self) -> List[int]:\n",
    "        _ans = self.ans\n",
    "\n",
    "        return [num for num in _ans if num != 0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # sum1[i][j] 是从位置 (i-1, j-1)开始往左上方走，走到边界为止的所有格子的元素和。\n",
    "        sum1 = [[0] * (n + 2) for _ in range(m + 1)]  \n",
    "        # sum2[i][j] 是从位置(i-1, j-1)开始往右上方走，走到边界为止的所有格子的元素和。\n",
    "        sum2 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                sum1[i][j] = sum1[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "                sum2[i][j] = sum2[i - 1][j + 1] + grid[i - 1][j - 1]\n",
    "        \n",
    "        ans = Answer()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 单独的一个格子也是菱形\n",
    "                ans.put(grid[i][j])\n",
    "                for k in range(i + 2, m, 2):\n",
    "                    ux, uy = i, j\n",
    "                    dx, dy = k, j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    \n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    \n",
    "                    ans.put(\n",
    "                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +\n",
    "                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +\n",
    "                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +\n",
    "                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -\n",
    "                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])\n",
    "                    )\n",
    "        \n",
    "        return ans.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0, 0, 0]\n",
    "    \n",
    "    def put(self, x):\n",
    "        _ans = self.ans\n",
    "\n",
    "        if x > _ans[0]:\n",
    "            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1], _ans[2] = x, _ans[1]\n",
    "        elif x != _ans[0] and x!= _ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    \n",
    "    def get(self):\n",
    "        _ans = self.ans\n",
    "        return [num for num in _ans if num != 0]\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "\n",
    "        ans = Answer()\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        sum1 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "        sum2 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1]\n",
    "                sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1]\n",
    "\n",
    "        ls = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans.put(grid[i][j])\n",
    "                # 下一个顶点的坐标\n",
    "                for k in range(i+2, m, 2):\n",
    "                    tx, ty = i, j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    bx, by = k, j\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    # 顶点不一定是满足边界的\n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    # 区间的值，可以由边界的值-开始的值得到\n",
    "\n",
    "                    l1 = sum2[lx+1][ly+1] - sum2[tx][ty+2]\n",
    "                    l2 = sum1[rx+1][ry+1] - sum1[tx][ty]\n",
    "                    l3 = sum1[bx+1][by+1] - sum1[lx][ly]\n",
    "                    l4 = sum2[bx+1][by+1] - sum2[rx][ry+2]\n",
    "                    p4 = grid[tx][ty] + grid[lx][ly] + grid[rx][ry] + grid[bx][by]\n",
    "                    ans.put(l1 + l2 + l3 + l4 - p4)\n",
    "\n",
    "        return ans.get()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0,0,0]\n",
    "    def put(self,x):\n",
    "        ans_ = self.ans\n",
    "        if x > ans_[0]:\n",
    "            ans_[0],ans_[1],ans_[2] = x,ans_[0],ans_[1]\n",
    "        elif x != ans_[0] and x > ans_[1]:\n",
    "            ans_[1],ans_[2] = x,ans_[1]\n",
    "        elif x != ans_[0] and x != ans_[1] and x > ans_[2]:\n",
    "            ans_[2] = x\n",
    "    def out(self):\n",
    "        ans_ = self.ans\n",
    "        return [num for num in ans_ if num!=0]\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # l_u[i][j]表示以坐标[i-1][j-1]为起点的左上的元素和\n",
    "        l_u = [[0]*(n+2) for i in range(m+1)]\n",
    "        # r_u[i][j]表示以坐标[i-1][j-1]为起点的右上的元素和\n",
    "        r_u = [[0]*(n+2) for i in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                l_u[i][j] = l_u[i-1][j+1]+grid[i-1][j-1]\n",
    "                r_u[i][j] = r_u[i-1][j-1]+grid[i-1][j-1]\n",
    "        ans = Answer()\n",
    "        # 枚举菱形上顶点和水平宽度\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 将单个格子放入\n",
    "                ans.put(grid[i][j])\n",
    "                for k in range(i+2,m,2):\n",
    "                    ux,uy = i,j\n",
    "                    dx,dy = k,j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    # 统计结果\n",
    "                    ans.put(\n",
    "                        (l_u[lx + 1][ly + 1] - l_u[ux][uy + 2]) +\n",
    "                        (r_u[rx + 1][ry + 1] - r_u[ux][uy]) +\n",
    "                        (r_u[dx + 1][dy + 1] - r_u[lx][ly]) +\n",
    "                        (l_u[dx + 1][dy + 1] - l_u[rx][ry + 2]) -\n",
    "                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry]))\n",
    "        return ans.out()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0,0,0]\n",
    "    def put(self,x):\n",
    "        _ans = self.ans\n",
    "        if x > _ans[0]:\n",
    "            _ans[0],_ans[1],_ans[2] = x,_ans[0],_ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1],_ans[2] = x,_ans[1]\n",
    "        elif x != _ans[0] and x!=_ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    def get(self):\n",
    "        _ans = self.ans\n",
    "        return [num for num in _ans if num != 0]\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 预处理\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        sum1 = [[0]*(n+2) for _ in range(m+1)] # sum1[i][j]表示从坐标为 （i-1,j-1）往左上方走走到边界的元素和\n",
    "        sum2 = [[0]*(n+2) for _ in range(m+1)] # sum2[i][j]表示从坐标为 （i-1,j-1）往右边上方走走到边界的元素和\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1]\n",
    "                sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1]\n",
    "        ans = Answer()\n",
    "        # 枚举顶点位置\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans.put(grid[i][j])\n",
    "                # 枚举菱形水平方向的宽度\n",
    "                for k in range(i+2,m,2):\n",
    "                    ux,uy = i,j\n",
    "                    dx,dy = k,j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    # 统计结果\n",
    "                    ans.put(\n",
    "                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +\n",
    "                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +\n",
    "                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +\n",
    "                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -\n",
    "                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry]))\n",
    "\n",
    "        return ans.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0] * 3\n",
    "    \n",
    "    def put(self, x):\n",
    "        _ans = self.ans\n",
    "\n",
    "        if x > _ans[0]:\n",
    "            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1], _ans[2] = x, _ans[1]\n",
    "        elif x!= _ans[0] and x != _ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    \n",
    "    def get(self):\n",
    "        _ans = self.ans\n",
    "        return [x for x in _ans if x != 0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        sum1 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "        sum2 = [[0] * (n + 2) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n + 1):\n",
    "                sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1]\n",
    "                sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1]\n",
    "        \n",
    "        ans = Answer()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans.put(grid[i][j])\n",
    "                for k in range(i+2, m, 2):\n",
    "                    ux, uy = i, j\n",
    "                    dx, dy = k, j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    # 处y理越界情况\n",
    "                    if ly < 0 or ry >n-1:\n",
    "                        break\n",
    "                    \n",
    "                    # 计算4条线和点的值\n",
    "                    l1 = sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]\n",
    "                    l2 = sum1[rx + 1][ry + 1] - sum1[ux][uy]\n",
    "                    l3 = sum1[dx + 1][dy + 1] - sum1[lx][ly]\n",
    "                    l4 = sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]\n",
    "                    p4 = grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry]\n",
    "                    ans.put(l1 + l2 + l3 + l4 - p4)\n",
    "    \n",
    "        return ans.get()\n",
    "                             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.ans = [0,0,0]\n",
    "    def put(self,x):\n",
    "        _ans = self.ans\n",
    "        if x > _ans[0]:\n",
    "            _ans[0],_ans[1],_ans[2] = x,_ans[0],_ans[1]\n",
    "        elif x != _ans[0] and x > _ans[1]:\n",
    "            _ans[1],_ans[2] = x,_ans[1]\n",
    "        elif x != _ans[0] and x!=_ans[1] and x > _ans[2]:\n",
    "            _ans[2] = x\n",
    "    def get(self):\n",
    "        _ans = self.ans\n",
    "        return [num for num in _ans if num != 0]\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 预处理\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        sum1 = [[0]*(n+2) for _ in range(m+1)] # sum1[i][j]表示从坐标为 （i-1,j-1）往左上方走走到边界的元素和\n",
    "        sum2 = [[0]*(n+2) for _ in range(m+1)] # sum2[i][j]表示从坐标为 （i-1,j-1）往右边上方走走到边界的元素和\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1]\n",
    "                sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1]\n",
    "        ans = Answer()\n",
    "        # 枚举顶点位置\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans.put(grid[i][j])\n",
    "                # 枚举菱形水平方向的宽度\n",
    "                for k in range(i+2,m,2):\n",
    "                    ux,uy = i,j\n",
    "                    dx,dy = k,j\n",
    "                    lx, ly = (i + k) // 2, j - (k - i) // 2\n",
    "                    rx, ry = (i + k) // 2, j + (k - i) // 2\n",
    "                    if ly < 0 or ry >= n:\n",
    "                        break\n",
    "                    # 统计结果\n",
    "                    ans.put(\n",
    "                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +\n",
    "                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +\n",
    "                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +\n",
    "                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -\n",
    "                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry]))\n",
    "\n",
    "        return ans.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        def getS(i, j, d):\n",
    "            if d == 0:\n",
    "                return grid[i][j]\n",
    "            s = grid[i - d][j] + grid[i + d][j] + grid[i][j - d] + grid[i][j + d]\n",
    "            for k in range(1, d):\n",
    "                l, r = j - d + k, j + d - k\n",
    "                s += grid[i + k][l] + grid[i + k][r] + grid[i - k][l] + grid[i - k][r]\n",
    "            return s\n",
    "\n",
    "        ans = []\n",
    "        vis = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for d in range((min(m, n) + 1) // 2):\n",
    "            for i in range(m):\n",
    "                if i - d < 0 or i + d >= m:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if j - d < 0 or j + d >= n:\n",
    "                        continue\n",
    "                    s = getS(i, j, d)\n",
    "                    if s in vis:\n",
    "                        continue\n",
    "                    vis.add(s)\n",
    "                    heapq.heappush(ans, s)\n",
    "                    if len(ans) > 3:\n",
    "                        heapq.heappop(ans)\n",
    "        ans.sort(reverse=True)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = set()\n",
    "\n",
    "        # 枚举所有的菱形\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 添加面积为0的菱形\n",
    "                res.add(grid[i][j])\n",
    "                # 以当前点为中心，菱形的最大范围，上下左右的最小距离\n",
    "                length = min(i, j, m-1-i, n-1-j)\n",
    "                for l in range(1, length+1):\n",
    "                    cur = 0\n",
    "                    # 先加四个角\n",
    "                    cur += grid[i-l][j]\n",
    "                    cur += grid[i+l][j]\n",
    "                    cur += grid[i][j-l]\n",
    "                    cur += grid[i][j+l]\n",
    "                    # 再加上其它边上的元素\n",
    "                    for k in range(1, l):\n",
    "                        cur += grid[i-l+k][j+k] # 右上\n",
    "                        cur += grid[i+l-k][j+k] # 右下\n",
    "                        cur += grid[i-l+k][j-k] # 左上\n",
    "                        cur += grid[i+l-k][j-k] # 左下\n",
    "                    # 加上当前矩形\n",
    "                    res.add(cur)\n",
    "        \n",
    "        # 排序以后返回最大的三个\n",
    "        res = list(res)\n",
    "        res.sort(reverse=True)\n",
    "        return res[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        Row,  Col = len(grid), len(grid[0])\n",
    "        maxLen = min(Row, Col)\n",
    "        \n",
    "        val_set = set()\n",
    "        \n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                val_set.add(grid[r][c])\n",
    "        \n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                for Len in range(1, maxLen + 1):\n",
    "                    U = r - Len\n",
    "                    D = r + Len \n",
    "                    L = c - Len\n",
    "                    R = c + Len\n",
    "                    if (0 <= U)  and (D < Row) and (0 <= L) and (R < Col):\n",
    "                        cur_sum = grid[r][L]    #最左点\n",
    "                        r0,c0 = r-1, L+1\n",
    "                        while r0 > U:\n",
    "                            cur_sum += grid[r0][c0]\n",
    "                            r0 -= 1\n",
    "                            c0 += 1\n",
    "                        cur_sum += grid[U][c]   #最上点\n",
    "                        r0, c0 = U+1, c+1\n",
    "                        while r0 < r:\n",
    "                            cur_sum += grid[r0][c0]\n",
    "                            r0 += 1\n",
    "                            c0 += 1\n",
    "                        cur_sum += grid[r][R]   #最右点\n",
    "                        r0, c0 = r+1, R-1\n",
    "                        while r0 < D:\n",
    "                            cur_sum += grid[r0][c0]\n",
    "                            r0 += 1\n",
    "                            c0 -= 1\n",
    "                        cur_sum += grid[D][c]   #最下点\n",
    "                        r0, c0 = D-1, c-1\n",
    "                        while r0 > r:\n",
    "                            cur_sum += grid[r0][c0]\n",
    "                            r0 -= 1\n",
    "                            c0 -= 1\n",
    "                        val_set.add(cur_sum)\n",
    "                            \n",
    "                    else:\n",
    "                        break\n",
    "        a = list(val_set)\n",
    "        a.sort(reverse = True)\n",
    "        if len(a) < 3:\n",
    "            return a\n",
    "        else:\n",
    "            return a[:3]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        h = []\n",
    "        s = {-math.inf}\n",
    "\n",
    "        def topk(v: int):\n",
    "            if v in s:\n",
    "                return\n",
    "\n",
    "            s.add(v)\n",
    "            if len(h) < 3:\n",
    "                heappush(h, v)\n",
    "            else:\n",
    "                heappushpop(h, v)\n",
    "\n",
    "        def sum(r, c, w) -> int:\n",
    "            if w == 0:\n",
    "                return grid[r][c]\n",
    "\n",
    "            if r + 2 * w >= m or c - w < 0 or c + w >= n:\n",
    "                # print(f'({r},{c},{w}) 无效区域')\n",
    "                return -math.inf\n",
    "\n",
    "            tot = grid[r][c]\n",
    "            for i in range(1, w + 1):\n",
    "                tot += grid[r+i][c-i] + grid[r+i][c+i]\n",
    "\n",
    "            tot += grid[r + 2*w][c]\n",
    "            for i in range(1, w):\n",
    "                tot += grid[r + 2*w - i][c-i] + grid[r + 2*w - i][c+i]\n",
    "            #print(f'(r,c,w):{tot}')\n",
    "            return tot\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                for w in range(min(m, n) + 1):\n",
    "                    topk(sum(r, c, w))\n",
    "\n",
    "        return sorted([v for v in h], reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=[]\n",
    "        vis=set()\n",
    "        heappush(q,0)\n",
    "        heappush(q,0)\n",
    "        heappush(q,0)\n",
    "        def gets(x,y,s):\n",
    "            if not s:\n",
    "                return grid[x][y]\n",
    "            res=0\n",
    "            for i in range(x-s,x):\n",
    "                d=i-(x-s)\n",
    "                res+=grid[i][y+d]\n",
    "                res+=grid[i][y-d]\n",
    "            res-=grid[x-s][y]\n",
    "            for i in range(x+s,x,-1):\n",
    "                d=x+s-i\n",
    "                res+=grid[i][y+d]\n",
    "                res+=grid[i][y-d]\n",
    "            res-=grid[x+s][y]\n",
    "            # #\n",
    "            res+=grid[x][y+s]\n",
    "            res+=grid[x][y-s]\n",
    "            return res\n",
    "        for size in range((min(m,n)-1)//2 + 1):\n",
    "            for x in range(size,m-size):\n",
    "                for y in range(size,n-size):\n",
    "                    res=gets(x,y,size)\n",
    "                    if res in vis:\n",
    "                        continue\n",
    "                    vis.add(res)\n",
    "                    if q[0]<=res:\n",
    "                        heapreplace(q,res)\n",
    "        return sorted([c for c in q if c], reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        def getS(i, j, d):\n",
    "            if d == 0:\n",
    "                return grid[i][j]\n",
    "            s = grid[i - d][j] + grid[i + d][j] + grid[i][j - d] + grid[i][j + d]\n",
    "            for k in range(1, d):\n",
    "                l, r = j - d + k, j + d - k\n",
    "                s += grid[i + k][l] + grid[i + k][r] + grid[i - k][l] + grid[i - k][r]\n",
    "            return s\n",
    "\n",
    "        ans = []\n",
    "        vis = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for d in range((min(m, n) + 1) // 2):\n",
    "            for i in range(m):\n",
    "                if i - d < 0 or i + d >= m:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if j - d < 0 or j + d >= n:\n",
    "                        continue\n",
    "                    s = getS(i, j, d)\n",
    "                    if s in vis:\n",
    "                        continue\n",
    "                    vis.add(s)\n",
    "                    heapq.heappush(ans, s)\n",
    "                    if len(ans) > 3:\n",
    "                        heapq.heappop(ans)\n",
    "        return sorted(ans, reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res.add(grid[i][j])\n",
    "                length = min(i, j, m-1-i, n-1-j)\n",
    "                for l in range(1, length+1):\n",
    "                    cur = 0\n",
    "                    cur += grid[i-l][j]\n",
    "                    cur += grid[i+l][j]\n",
    "                    cur += grid[i][j-l]\n",
    "                    cur += grid[i][j+l]\n",
    "                    for k in range(1, l):\n",
    "                        cur += grid[i-k][j-l+k]\n",
    "                        cur += grid[i-k][j+l-k]\n",
    "                        cur += grid[i+k][j+l-k]\n",
    "                        cur += grid[i+k][j-l+k]\n",
    "                    res.add(cur)\n",
    "            \n",
    "        res = list(res)\n",
    "        res.sort(reverse=True)\n",
    "        return res[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=[]\n",
    "        vis=set()\n",
    "        heappush(q,0)\n",
    "        heappush(q,0)\n",
    "        heappush(q,0)\n",
    "        def gets(x,y,s):\n",
    "            if not s:\n",
    "                return grid[x][y]\n",
    "            res=0\n",
    "            for i in range(x-s,x):\n",
    "                d=i-(x-s)\n",
    "                res+=grid[i][y+d]\n",
    "                res+=grid[i][y-d]\n",
    "            res-=grid[x-s][y]\n",
    "            for i in range(x+s,x,-1):\n",
    "                d=x+s-i\n",
    "                res+=grid[i][y+d]\n",
    "                res+=grid[i][y-d]\n",
    "            res-=grid[x+s][y]\n",
    "            # #\n",
    "            res+=grid[x][y+s]\n",
    "            res+=grid[x][y-s]\n",
    "            return res\n",
    "        for size in range((min(m,n)-1)//2 + 1):\n",
    "            for x in range(size,m-size):\n",
    "                for y in range(size,n-size):\n",
    "                    res=gets(x,y,size)\n",
    "                    if res in vis:\n",
    "                        continue\n",
    "                    vis.add(res)\n",
    "                    if q[0]<=res:\n",
    "                        heapreplace(q,res)\n",
    "        return sorted([c for c in q if c], reverse=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = ((1, 1), (1, -1), (-1, -1), (-1, 1))\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        ans = set()\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                for d in range(1, (min(n, m) + 1) // 2 + 1):\n",
    "                    if d == 1:\n",
    "                        ans.add(grid[i][j])\n",
    "                        continue\n",
    "\n",
    "                    d -= 1\n",
    "                    ok = True\n",
    "                    l, r, b = (i + d, j - d), (i + d, j + d), (i + 2 * d, j)\n",
    "                    for ni, nj in (l, r, b):\n",
    "                        if not (0 <= ni < n and 0 <= nj < m):\n",
    "                            ok = False\n",
    "                            break\n",
    "                    if not ok: break\n",
    "\n",
    "                    destinations = [r, b, l, (i, j)]\n",
    "                    s = 0\n",
    "                    for k, (ni, nj) in enumerate(dirs):\n",
    "                        while True:\n",
    "                            s += grid[i][j]\n",
    "                            if (i, j) == destinations[k]:\n",
    "                                s -= grid[i][j]\n",
    "                                break\n",
    "                            i += ni; j += nj\n",
    "                    ans.add(s)\n",
    "\n",
    "        return sorted(ans, reverse=True)[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "                    \n",
    "            \n",
    "                    m,n = len(grid),len(grid[0])\n",
    "                    q = set();t = max(m,n)\n",
    "                    for i in range(m):\n",
    "                        for j in range(n):\n",
    "                            cnm = grid[i][j]\n",
    "                            for dd in range(1,51):\n",
    "                                a,b,c,d = i - dd,j - dd,i + dd,j + dd\n",
    "                                cc = 0\n",
    "                                jj = j;ii = a\n",
    "                                if 0 <= a < m and 0 <= b < n and 0 <= c < m and 0 <= d < n:\n",
    "                                    while a < i:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        a += 1\n",
    "                                        jj += 1\n",
    "                                    while a < c:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        a += 1\n",
    "                                        jj -= 1\n",
    "                                    while a > i:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        a -= 1\n",
    "                                        jj -= 1\n",
    "                                    while a > ii:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        jj += 1\n",
    "                                        a -= 1\n",
    "                                if cc:\n",
    "                                    q.add(cc)\n",
    "                            q.add(cnm)\n",
    "                    q = sorted(list(q),reverse = True)\n",
    "                    if len(q) < 3:\n",
    "                        return q\n",
    "                    return q[:3]\n",
    "                                        \n",
    "                                        \n",
    "                            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        ls = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                ls.add(grid[i][j])\n",
    "                sums = grid[i][j]\n",
    "                for k in range(1, min(j, (len(grid) - i - 1) // 2, len(grid[0]) - j - 1) + 1):\n",
    "                    sums += grid[i + k][j - k] + grid[i + k][j + k]\n",
    "                    bs = 0\n",
    "                    for l in range(1, k):\n",
    "                        bs += grid[i + k + l][j - k + l] + grid[i + k + l][j + k - l]\n",
    "                    ls.add(sums + bs + grid[i + k * 2][j])\n",
    "        return sorted(list(ls), reverse=True)[:3]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 暴力枚举所有情况，使用对角前缀和来快速计算每个边的总和\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 从左往右的对角线，从右往左的对角线\n",
    "        a = [[[0] * 2 for _ in range(n)] for _ in range(m)]\n",
    "        # 计算对角线的前缀和\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a[i][j][0] = grid[i][j] + (a[i - 1][j - 1][0] if i > 0 and j > 0 else 0)\n",
    "                a[i][j][1] = grid[i][j] + (a[i - 1][j + 1][1] if i > 0 and j < n - 1 else 0)\n",
    "\n",
    "        def val(i: int, j: int, i1: int, j1: int, d: int) -> int:\n",
    "            return a[i1][j1][d] - a[i][j][d] + grid[i][j]\n",
    "        \n",
    "        def valid(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "        def cal(i: int, j: int, l: int) -> int:\n",
    "            if l == 1:\n",
    "                return grid[i][j]\n",
    "            # 计算4个坐标,按顺时针方向\n",
    "            i1, j1 = i + l - 1, j + l - 1\n",
    "            i2, j2 = i1 + l - 1, j\n",
    "            i3, j3 = i1, j - l + 1\n",
    "            if valid(i1, j1) and valid(i2, j2) and valid(i3, j3):\n",
    "                return val(i, j, i1, j1, 0) + val(i1, j1, i2, j2, 1) + val(i3, j3, i2, j2, 0) + val(i, j, i3, j3, 1) - grid[i][j] - grid[i1][j1] - grid[i2][j2] - grid[i3][j3]\n",
    "            return 0\n",
    "        ans = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 2*l - 2 == min(m,n)\n",
    "                for l in range(1, (min(m, n) + 2) // 2 + 1):\n",
    "                    ans.add(cal(i, j, l))\n",
    "        # print(f'ans:{ans}')\n",
    "        ans = list(ans)\n",
    "        ans.sort(reverse=True)\n",
    "        return ans[:3] if len(ans)>=3 else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "                    \n",
    "            \n",
    "                    m,n = len(grid),len(grid[0])\n",
    "                    q = set();t = max(m,n)\n",
    "                    for i in range(m):\n",
    "                        for j in range(n):\n",
    "                            cnm = grid[i][j]\n",
    "                            for dd in range(1,101):\n",
    "                                a,b,c,d = i - dd,j - dd,i + dd,j + dd\n",
    "                                cc = 0\n",
    "                                jj = j;ii = a\n",
    "                                if 0 <= a < m and 0 <= b < n and 0 <= c < m and 0 <= d < n:\n",
    "                                    while a < i:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        a += 1\n",
    "                                        jj += 1\n",
    "                                    while a < c:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        a += 1\n",
    "                                        jj -= 1\n",
    "                                    while a > i:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        a -= 1\n",
    "                                        jj -= 1\n",
    "                                    while a > ii:\n",
    "                                        cc += grid[a][jj]\n",
    "                                        jj += 1\n",
    "                                        a -= 1\n",
    "                                if cc:\n",
    "                                    q.add(cc)\n",
    "                            q.add(cnm)\n",
    "                    q = sorted(list(q),reverse = True)\n",
    "                    if len(q) < 3:\n",
    "                        return q\n",
    "                    return q[:3]\n",
    "                                        \n",
    "                                        \n",
    "                            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 暴力枚举所有情况，使用对角前缀和来快速计算每个边的总和\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 从左往右的对角线，从右往左的对角线\n",
    "        a = [[[0] * 2 for _ in range(n)] for _ in range(m)]\n",
    "        # 计算对角线的前缀和\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a[i][j][0] = grid[i][j] + (a[i - 1][j - 1][0] if i > 0 and j > 0 else 0)\n",
    "                a[i][j][1] = grid[i][j] + (a[i - 1][j + 1][1] if i > 0 and j < n - 1 else 0)\n",
    "\n",
    "        def val(i: int, j: int, i1: int, j1: int, d: int) -> int:\n",
    "            return a[i1][j1][d] - a[i][j][d] + grid[i][j]\n",
    "        \n",
    "        def valid(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "        def cal(i: int, j: int, l: int) -> int:\n",
    "            if l == 1:\n",
    "                return grid[i][j]\n",
    "            # 计算4个坐标,按顺时针方向\n",
    "            i1, j1 = i + l - 1, j + l - 1\n",
    "            i2, j2 = i1 + l - 1, j\n",
    "            i3, j3 = i1, j - l + 1\n",
    "            if valid(i1, j1) and valid(i2, j2) and valid(i3, j3):\n",
    "                return val(i, j, i1, j1, 0) + val(i1, j1, i2, j2, 1) + val(i3, j3, i2, j2, 0) + val(i, j, i3, j3, 1) - grid[i][j] - grid[i1][j1] - grid[i2][j2] - grid[i3][j3]\n",
    "            return 0\n",
    "        ans = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 2*l - 2 == min(m,n)\n",
    "                for l in range(1, min(m, n) + 1):\n",
    "                    ans.add(cal(i, j, l))\n",
    "        # print(f'ans:{ans}')\n",
    "        ans = list(ans)\n",
    "        ans.sort(reverse=True)\n",
    "        return ans[:3] if len(ans)>=3 else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 暴力枚举所有情况，使用对角前缀和来快速计算每个边的总和\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 从左往右的对角线，从右往左的对角线\n",
    "        a = [[[0] * 2 for _ in range(n)] for _ in range(m)]\n",
    "        # 计算对角线的前缀和\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a[i][j][0] = grid[i][j] + (a[i - 1][j - 1][0] if i > 0 and j > 0 else 0)\n",
    "                a[i][j][1] = grid[i][j] + (a[i - 1][j + 1][1] if i > 0 and j < n - 1 else 0)\n",
    "\n",
    "        def val(i: int, j: int, i1: int, j1: int, d: int) -> int:\n",
    "            return a[i1][j1][d] - a[i][j][d] + grid[i][j]\n",
    "        \n",
    "        def valid(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "        def cal(i: int, j: int, l: int) -> int:\n",
    "            if l == 1:\n",
    "                return grid[i][j]\n",
    "            # 计算4个坐标,按顺时针方向\n",
    "            i1, j1 = i + l - 1, j + l - 1\n",
    "            i2, j2 = i1 + l - 1, j\n",
    "            i3, j3 = i1, j - l + 1\n",
    "            if valid(i1, j1) and valid(i2, j2) and valid(i3, j3):\n",
    "                return val(i, j, i1, j1, 0) + val(i1, j1, i2, j2, 1) + val(i3, j3, i2, j2, 0) + val(i, j, i3, j3, 1) - grid[i][j] - grid[i1][j1] - grid[i2][j2] - grid[i3][j3]\n",
    "            return 0\n",
    "        ans = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 2*l - 2 == min(m,n)\n",
    "                for l in range(1, (min(m, n) + 2) // 2 + 1):\n",
    "                    ans.add(cal(i, j, l))\n",
    "        # print(f'ans:{ans}')\n",
    "        ans = list(ans)\n",
    "        ans.sort(reverse=True)\n",
    "        return ans[:3] if len(ans)>=3 else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n, s = len(grid), len(grid[0]), set()\n",
    "        pre1, pre2 = [[0] * (n + 2) for _ in range(m + 2)], [[0] * (n + 2) for _ in range(m + 2)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre1[i + 1][j + 1], pre2[i + 1][j + 1] = pre1[i][j] + grid[i][j], pre2[i][j + 2] + grid[i][j]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                s.add(grid[i - 1][j - 1])\n",
    "                for k in range(1, min(m - i + 1, n - j + 1)):\n",
    "                    if i - k < 1 or j - k < 1:\n",
    "                        break\n",
    "                    s.add(pre2[i][j - k] - pre2[i - k][j] + pre1[i][j + k] - pre1[i - k][j] + pre2[i + k][j] - pre2[i][j + k] + pre1[i + k][j] - pre1[i][j - k] - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1])\n",
    "        return sorted(list(s), reverse=True)[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: list[list[int]]) -> list[int]:\n",
    "        def judge(p):\n",
    "            x,y = p\n",
    "            return  x in range(m) and y in range(n)\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans.append(grid[i][j])\n",
    "                for k in range(1,max(m,n)//2+1):\n",
    "                    p1 = (i,j)\n",
    "                    p2 = (i+k,j-k)\n",
    "                    p3 = (i+2*k,j)\n",
    "                    p4 = (i+k,j+k)\n",
    "                    if judge(p1) and judge(p2) and judge(p3) and judge(p4):\n",
    "                        tot = grid[p1[0]][p1[1]]+grid[p2[0]][p2[1]]+grid[p3[0]][p3[1]]+grid[p4[0]][p4[1]]\n",
    "                        for l in range(1,k):\n",
    "                            tot += grid[i+l][j-l]+grid[i+l][j+l]+grid[i+2*k-l][j-l]+grid[i+2*k-l][j+l]\n",
    "                        ans.append(tot)\n",
    "                    else:\n",
    "                        break\n",
    "        ans = list(set(ans))\n",
    "        ans.sort(reverse = True)\n",
    "        if len(ans)<=3:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 矩阵斜向前缀和/对角线前缀和/斜对角线前缀和\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "\n",
    "DIR4 = [[-1, 0], [0, -1], [1, 0], [0, 1]]\n",
    "Point = Tuple[int, int]\n",
    "\n",
    "\n",
    "class DiagonalPresum:\n",
    "    \"\"\"二维矩阵对角线前缀和\"\"\"\n",
    "\n",
    "    __slots__ = \"_preSum1\", \"_preSum2\"\n",
    "\n",
    "    def __init__(self, matrix: List[List[int]]):\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        preSum1 = [[0] * (col + 1) for _ in range(row + 1)]  # 主对角线前缀和 ↘\n",
    "        preSum2 = [[0] * (col + 1) for _ in range(row + 1)]  # 反对角线前缀和 ↙\n",
    "        for i, r in enumerate(matrix):\n",
    "            tmp1 = preSum1[i]\n",
    "            tmp2 = preSum1[i + 1]\n",
    "            tmp3 = preSum2[i]\n",
    "            tmp4 = preSum2[i + 1]\n",
    "            for j, v in enumerate(r):\n",
    "                tmp2[j + 1] = tmp1[j] + v\n",
    "                tmp4[j] = tmp3[j + 1] + v\n",
    "\n",
    "        self._preSum1 = preSum1\n",
    "        self._preSum2 = preSum2\n",
    "\n",
    "    def queryDiagonal(self, leftUp: Point, rightDown: Point) -> int:\n",
    "        \"\"\"正对角线左上角到右下角的前缀和.\"\"\"\n",
    "        r1, c1, r2, c2 = *leftUp, *rightDown\n",
    "        return self._preSum1[r2 + 1][c2 + 1] - self._preSum1[r1][c1]\n",
    "\n",
    "    def queryAntiDiagonal(self, leftDown: Point, rightUp: Point) -> int:\n",
    "        \"\"\"副对角线左下角到右上角的前缀和\"\"\"\n",
    "        r1, c1, r2, c2 = *leftDown, *rightUp\n",
    "        return self._preSum2[r1 + 1][c1] - self._preSum2[r2][c2 + 1]\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    from heapq import nlargest\n",
    "\n",
    "    # 1878. 矩阵中最大的三个菱形和\n",
    "    # LC1878 https://leetcode-cn.com/problems/get-biggest-three-rhombus-sums-in-a-grid/\n",
    "    # 按照 降序 返回 grid 中三个最大的 互不相同的菱形和.\n",
    "    # 如果不同的和少于三个，则将它们全部返回。\n",
    "    class Solution:\n",
    "        def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "            \"\"\"对角线前缀和\"\"\"\n",
    "\n",
    "            def calSum(up: Point, left: Point, down: Point, right: Point) -> int:\n",
    "                return (\n",
    "                    (\n",
    "                        dp.queryDiagonal(up, right)\n",
    "                        + dp.queryAntiDiagonal(left, up)\n",
    "                        + dp.queryDiagonal(left, down)\n",
    "                        + dp.queryAntiDiagonal(down, right)\n",
    "                    )\n",
    "                    - grid[up[0]][up[1]]\n",
    "                    - grid[left[0]][left[1]]\n",
    "                    - grid[down[0]][down[1]]\n",
    "                    - grid[right[0]][right[1]]\n",
    "                )\n",
    "\n",
    "            ROW, COL = len(grid), len(grid[0])\n",
    "            res = set()\n",
    "\n",
    "            # 对角线前缀和矩阵\n",
    "            dp = DiagonalPresum(grid)\n",
    "            for r in range(ROW):\n",
    "                for c in range(COL):\n",
    "                    res.add(grid[r][c])\n",
    "                    for side in range(1, int(1e20)):\n",
    "                        up, left, down, right = [(r + side * dr, c + side * dc) for dr, dc in DIR4]\n",
    "                        if not all(\n",
    "                            0 <= nr < ROW and 0 <= nc < COL for nr, nc in [up, left, down, right]\n",
    "                        ):\n",
    "                            break\n",
    "                        res.add(calSum(up, left, down, right))\n",
    "\n",
    "            return nlargest(3, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def _sum(x1,x2,x3,x4,y1,y2,y3,y4):\n",
    "            ans = 0\n",
    "            ans += grid[x1][y1] + grid[x2][y2] + grid[x3][y3] + grid[x4][y4]\n",
    "            for k in range(1, x2 - x1):\n",
    "                ans += grid[x1+k][y1-k] + grid[x1+k][y1+k] + grid[x3-k][y1-k] + grid[x3-k][y1+k]\n",
    "            return ans\n",
    "\n",
    "        def judge(x1, y1, x2, y2):\n",
    "            x3, y3 = x2-x1+x2, y1\n",
    "            x4, y4 = x2, y1 + y1- y2\n",
    "            if x3 >=0 and x3 < m and x4>=0 and x4<m and y3>=0 and y3<n and y4>=0 and y4<n:\n",
    "                return _sum(x1,x2,x3,x4,y1,y2,y3,y4)\n",
    "            return 0\n",
    "\n",
    "        lst = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                lst.append(grid[i][j])\n",
    "                x1, y1 = i, j\n",
    "                for k in range(1, 1 + min(m-i-1, j)):\n",
    "                    x2 = x1 + k\n",
    "                    y2 = y1 - k\n",
    "                    t = judge(x1,y1,x2,y2)\n",
    "                    if t != 0:\n",
    "                        lst.append(t)\n",
    "        lst = set(lst)\n",
    "\n",
    "        return heapq.nlargest(3, lst)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        seen=set()\n",
    "        ans=[]\n",
    "        upLimit=min(ceil(m/2),ceil(n/2))\n",
    "\n",
    "        def check(i,j,l):\n",
    "      \n",
    "            if l==1:\n",
    "                return grid[i][j]\n",
    "            diff=l-1\n",
    "            up=(i,j)\n",
    "            left=(i+diff,j-diff)\n",
    "            if not (0<=left[0]<m and 0<=left[1]<n):\n",
    "                return 0\n",
    "            \n",
    "            down=(left[0]+diff,left[1]+diff)\n",
    "            if not (0<=down[0]<m and 0<=down[1]<n):\n",
    "                return 0\n",
    "\n",
    "\n",
    "\n",
    "            right=(down[0]-diff,down[1]+diff)\n",
    "            if not (0<=right[0]<m and 0<=right[1]<n):\n",
    "                return 0\n",
    "\n",
    "            \n",
    "            cur=0\n",
    "            x=i\n",
    "            y=j\n",
    "      \n",
    "            while x!=left[0] and y!=left[1]:\n",
    "                cur+=grid[x][y]\n",
    "                x+=1\n",
    "                y-=1\n",
    "            \n",
    "     \n",
    "            while x!=down[0] and y!=down[1]:\n",
    "                cur+=grid[x][y]\n",
    "                x+=1\n",
    "                y+=1\n",
    "            \n",
    "  \n",
    "            while x!=right[0] and y!=right[1]:\n",
    "                cur+=grid[x][y]\n",
    "                x-=1\n",
    "                y+=1\n",
    "\n",
    "            while x!=up[0] and y!=up[1]:\n",
    "                cur+=grid[x][y]\n",
    "                x-=1\n",
    "                y-=1\n",
    "            return cur\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for l in range(1,upLimit+1):\n",
    "                    cur=check(i,j,l)\n",
    "                    if cur not in seen and cur!=0:\n",
    "                        ans.append(cur)\n",
    "                        seen.add(cur)\n",
    "        return sorted(ans)[::-1][:3]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:\r\n",
    "        import heapq\r\n",
    "        ans = []\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        directions = [[1, -1], [1, 1], [-1, 1], [-1, -1]]\r\n",
    "        prefix_dict = {}\r\n",
    "        begin_dict = {}\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if not (i == 0 or i == m - 1 or j == 0 or j == n - 1):\r\n",
    "                    continue\r\n",
    "                val = grid[i][j]\r\n",
    "                prefix_dict[(i, j)] = ([0, val], [0, val], [0, val], [0, val])\r\n",
    "                index_list = []\r\n",
    "                if i == 0:\r\n",
    "                    index_list = [0,1]\r\n",
    "                elif j == 0:\r\n",
    "                    index_list = [1,2]\r\n",
    "                elif i == m-1:\r\n",
    "                    index_list = [2,3]\r\n",
    "                elif j == n-1:\r\n",
    "                    index_list = [3,0]\r\n",
    "                # print(i, j, index_list)\r\n",
    "                for index in index_list:\r\n",
    "                    # print(\"\\n\",\"i,j:\",i,j,index,end=\":\")\r\n",
    "                    begin_dict[(i, j, index)] = (i, j)\r\n",
    "                    new_i = i + directions[index][0]\r\n",
    "                    new_j = j + directions[index][1]\r\n",
    "                    while new_i >= 0 and new_i < m and new_j >= 0 and new_j < n:\r\n",
    "                        begin_dict[(new_i, new_j, index)] = (i, j)\r\n",
    "                        # print((new_i, new_j),end=\"\")\r\n",
    "                        prefix_dict[(i, j)][index].append(\r\n",
    "                            prefix_dict[(i, j)][index][-1] + grid[new_i][new_j])\r\n",
    "                        new_i += directions[index][0]\r\n",
    "                        new_j += directions[index][1]\r\n",
    "        # print(prefix_dict)\r\n",
    "        # print(begin_dict)\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                ans.append(grid[i][j])\r\n",
    "                for l in range(1, min(m, n)):\r\n",
    "                    val = 0\r\n",
    "                    x = i\r\n",
    "                    y = j\r\n",
    "                    for index in range(4):\r\n",
    "                        new_i = x+l*directions[index][0]\r\n",
    "                        new_j = y+l*directions[index][1]\r\n",
    "                        if new_i >= 0 and new_i < m and new_j >= 0 and new_j < n and (new_i, new_j, index) in begin_dict:\r\n",
    "                            begin_index = begin_dict[(new_i, new_j, index)]\r\n",
    "                            prefix_list = prefix_dict[begin_index][index]\r\n",
    "                            index1 = (new_i-begin_index[0])//directions[index][0]\r\n",
    "                            index2 = (x-begin_index[0])//directions[index][0]\r\n",
    "                            val += prefix_list[max(index1, index2)+1] - prefix_list[min(index1, index2)+1]\r\n",
    "                            # print(x,y,new_i,new_j,l,index,val)\r\n",
    "                        else:\r\n",
    "                            val = 0\r\n",
    "                            break\r\n",
    "                        x = new_i\r\n",
    "                        y = new_j\r\n",
    "                    if val>0:\r\n",
    "                        ans.append(val)\r\n",
    "        ans = list(set(ans))\r\n",
    "        ans.sort()\r\n",
    "        print(ans)\r\n",
    "        # return ans[-3:]\r\n",
    "        return sorted(ans[-3:], key=cmp_to_key(lambda x, y: y-x))\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
